package leetcode每日一题;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 1. 问题描述
 *      给定一个无重复元素的有序整数数组 nums 。
 *      返回恰好覆盖数组中所有数字 的 最小有序 区间范围列表。
 *      也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
 *      列表中的每个区间范围 [a,b] 应该按如下格式输出：
 *          "a->b" ，如果 a != b
 *          "a" ，如果 a == b
 *
 * 2， 算法分析
 *      1. 线性扫描
 *          从头开始扫描数组，以当前元素为区间的头部，如果后面的元素恰好是前一个元素+1，则融入到区间中
 *          直到不满足，这个过程中需要记录当前所求的区间长度，如果为0，说明当前区间只有一个元素，返回“a”
 *          如果大于0，返回"a->b"
 *          时间复杂度为O(n) 空间复杂度O(1)
 *
 *      2.
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 汇总区间 {
    public static void main(String[] args) {

    }

    // 线性扫描
    public static List<String> summaryRanges1(int[] nums) {
        int len = nums.length; // 元素个数
        List<String> res = new ArrayList<>();
        for(int i = 0; i < len; i++) {
            int j = i; // 从当前元素开始向后扫描
            int temp = 0; // 记录从当前元素开始的区间长度
            while(j < len - 1 && nums[j] + 1 == nums[j+1]) {
                temp++;
                j++;
            }
            if(temp == 0) {
                // 区间长度为0
                res.add(nums[i]+"");
            } else {
                // 区间长度大于0
                res.add(nums[i]+"->"+nums[j]);
            }
            i = j; // 注意此处不需要+1，因为在for循环中会自增1，所以如果此处+1，会少判断一个元素
        }
        return res;
    }

    // 双指针
    public static List<String> summaryRanges2(int[] nums) {
        int i = 0;
        int j = 0;
        int len = nums.length;
        List<String> res = new ArrayList<>();
        if(len == 1) {
            res.add(nums[0]+"");
            return res;
        }
        while(i < len && j < len) { // 此时最后一个元素无法判断，如果是单个区间的话，所以需要单独判断
            while(j < len - 1 && nums[j] + 1 == nums[j+1]) {
                j++;
            }
            if(j - i == 0) {
                // 区间长度为0
                res.add(nums[i]+"");
                i++;
                j++;
            } else {
                res.add(nums[i]+"->"+nums[j]);
                j++;
                i = j;
            }
        }
        return res;
    }

    // 双指针的第二种形式：通过left和right记录区间的左右边界元素的索引  内存和效率是三个中最好的
    public static List<String> summaryRanges3(int[] nums) {
        int left = 0;
        int right = 0;
        List<String> res = new ArrayList<>();
        int len = nums.length;
        int i = 0; // 用于扫描数组中的元素
        while(i < len) {
            left = i; // 初始化左边界索引
            i++; // 从下一位开始于之前的一位进行比较
            while(i < len && nums[i] - 1 == nums[i-1]) {
                i++;
            }
            // 当循环退出的时候，说明当前i指向的元素与前面的元素只差大于1，所以区间在此断开
            right = i - 1; // i指向的前一个元素才是当前区间的右边界
            StringBuilder temp = new StringBuilder(Integer.toString(nums[left])); // 创建字符串流对象，节省内存
            if(left < right) { // 说明此时区间的长度大于0
                temp.append("->");
                temp.append(Integer.toString(nums[right]));
            }
            res.add(temp.toString());
        }
        return res;
    }

}
